Cyclic code error correcting systems for correcting random single-bit errors in a data word are well known in the art. The operation of cyclic codes is an extension of the basic Hamming code and can be explained from several perspectives. One accepted explanation involves a parity check table, such as that shown in FIG. 1, which involves a table having K rows and a maximum of 2.sup.K -1 columns. In the table of FIG. 1, there are eight rows and, hence, a maximum of 255 columns. If the X's in the table are replaced with binary 1's and the blanks in the table by binary 0's, a 255.times.8 binary matrix H is established which has the capability of detecting, locating and correcting single-bit errors which might occur in any one of the 255 sequential bit positions if a parity check bit is generated for each row from bit positions designated by an X in the table or a 1 in the matrix H.
In the table shown in FIG. 1, the rows have been labelled P0 through P7 starting from the bottom of the table, and the 255 bit positions labelled D0 through D246 and C247 through C254 moving from right to left. Bit positions C247 through C254 are assigned to a generated check character which is used to "protect" a string of 246 data bits that is stored in an environment which might cause one bit of the 255 to be in error when the data is operated on. Typically, the check character is generated again as the data is read from the storage. The newly generated check character is compared, or exclusive-OR'd with the previously generated check character to produce what is generally known in the art as a syndrome character S consisting of bits S0 through S7. An all-zero syndrome byte indicates no error, while a non-zero syndrome byte indicates either a single-bit error, the location of which is defined by the pattern of the non-zero syndrome byte, or an uncorrectable error. This can be readily seen in the parity check table of FIG. 1 since each column represents a unique syndrome byte pattern which will be generated when a single-bit error occurs in the data bit located at the corresponding bit position in the data stream.
In theory, the rules for generating or constructing the parity check table merely require that each column of the table be unique. From a mathematical perspective, each row of the parity check table can be written as a logical equation so that the modulo-2 sum of all bit positions containing an X is equal to 0. The group of eight rows, from a mathematical perspective, represent eight independent, simultaneous equations.
The use of the mathematical perspective assists in simplifying the implementation of a parity check table or matrix in actual hardware since the selection and arrangement of the various permutations of bit values can be accomplished in a more systematic manner. For example, the columns of the parity check matrix represent all possible permutations of eight bits except the all-zero pattern. As mentioned previously, the sequence of the permutations can be arbitrary, and the non-zero syndrome byte will still identify the location of the bit position in error. A linear 8-bit binary counter may provide all of the necessary permutations, but the art has shown that such an implementation involves the problem of certain check bits not being in their final state at the time that they are being checked by other check bits. The prior art, therefore, suggests the use of a maximal length sequence generator, such as the feedback shift register shown in FIG. 2, to implement the function of a parity check table. As is further taught in the art, the feedback connections can be defined mathematically by one of many polynomials. The output of each stage of the maximal length sequence generator or feedback shift register corresponds to an m-sequence. The sequence defined by any row of the table shown in FIG. 1 can also be expressed as a polynomial type equation, as shown in FIG. 2 where the initial status of the shift register contains the "x10" pattern, as shown.
The output of each stage of the feedback shift register can be used to simply sample the value of each data bit position and each parity bit position and the result accumulated modulo-2 to generate the check characters C247 through C254.
An article by the inventor appearing in the IBM Journal of Research and Development, Vol. 24, No. 1, January 1980, also discloses check character generators which employ premultiplier matrices T.sup..lambda. which function similarly to conventional feedback shift registers.
Feedback shift register implementations are generally used for generating the check character during the write process and the readback process, and a simple exclusive-OR function is generally employed in generating the syndrome byte. Various arrangements, such as a table lookup scheme or an arrangement for shifting the feedback shift register while counting the number of shifts until a pattern has developed in the shift register which matches the syndrome pattern, are employed for locating or determining the bit position in error. Various implementations based on the above two general concepts have been widely disclosed in the prior art.
It is also well known that the capability of the matrix H represented by the parity check table of FIG. 1 can be increased such that with a single syndrome byte, double errors can be detected (but not corrected) in addition to correcting single-bit errors.
Also, it has been recognized that a single syndrome byte can perform more than two purposes, such as correction of single-bit errors and detection of some multi-bit errors. It should be apparent that the function of correcting any type of error necessarily implies the ability to detect that error and also to locate such an error in order for it to be corrected.
It is also generally well known that the correcting capability of a parity check matrix can be increased by adding additional check bytes and generating corresponding syndrome bytes for the same set of data bits. However, the use of additional check bytes implies less efficiency of the code or higher costs. For example, if the code is to protect stored data, the storage capacity of the memory for user data is decreased. A similar decrease in efficiency occurs when a code word requiring several check bytes is used to protect a data word being transmitted from a receiver to a transmitter through a communication channel, since the channel is functionally equivalent to a memory in many respects.
The selection of a matrix H for error correcting purposes is based to a large extent on the knowledge of the type of errors that can be expected and the relationship of the possibility of each type of error occurring. These parameters change drastically depending on the particular environment or application to which the error correcting system is applied. The capability or power of the code is also chosen based on the resulting consequences of particular types of errors not being detectable or correctable. Overlying all of the above considerations is the ability to implement the detecting, locating, and correcting functions in hardware that is economical and corresponds in operating speed to the system to which it is applied.